// 85. 最大矩形


//!!! buggy
class Pair{
    constructor(public width:number,public row:number){}
}

function getMax(stack:Pair[]):number{
    let max = 0
    while(stack.length){
        const front = stack.shift()!
        const last = stack[stack.length-1]|| front
        max = Math.max(max,front.width*(last.row-front.row+1))
    }
    return max
}

function maximalRectangle(matrix: string[][]): number {
    const row = matrix.length
    if(row==0) return 0
    const col = matrix[0].length
    const cnt = new Array(row).fill(0).map(e=>new Array(col).fill(0))

    let max = 0
    for(let i=0;i<row;i++){
        let sum = 0
        for(let j=0;j<col;j++){
            sum = matrix[i][j] == '1' ? sum+1 : 0
            cnt[i][j] = sum
        }
    }

    for(let j=0;j<col;j++){
        let stack:Pair[] = []
        for(let i=0;i<row;i++){
            if(matrix[i][j]=='1'){
                const cur = cnt[i][j]
                let top = stack[stack.length-1]!
                const tmp = []
                while(stack.length&&cur<top.width){
                    stack.pop()
                    tmp.unshift(top)
                    top = stack[stack.length-1]!
                }
                //* 删除的时候看看是不是最大的
                top = tmp[0]
                let changed = i
                top && (max = Math.max(max,cur*(i-top.row+1),getMax(tmp)))
                top&& !stack.length && (changed=top.row)
                stack.push(new Pair(cur,changed))
            }else{
                max = Math.max(max,getMax(stack))
                stack = []
            }   
        }
        //* 最后可能剩下一堆递增的，从上到下进行统计
        max = Math.max(max,getMax(stack))
    }
    return max
};

console.log(maximalRectangle([["1","0","1","1","0","1"],["1","1","1","1","1","1"],["0","1","1","0","1","1"],["1","1","1","0","1","0"],["0","1","1","1","1","1"],["1","1","0","1","1","1"]]))